#include <stdio.h>

/*

 * 快速排序
 * 前提：从小到大排，用数组来实现
   *
 * 思想：
 * 每次找一个基准值pivot,  =====》看题目，要求选第几个
 * 将小于pivot放左边        划分
 * 大于pivot放右边
 * （pivot会变得有序）
 * 对左子序列 和 右子序列 进行上述操作   递归来实现
 * */

/*
 *

 * 函数名：quickSort
 * 输入：无序的数组  左右指针
 * 输出：无
 * */
   /*
 * * 将小于pivot放左边        划分
 * 大于pivot放右边
 * */

/*

 * 1.如果pivot设置的是左边第一个值的话，要先移动右指针
 * 2.如果采用数组内部位置进行交换的方式，需要注意等于的情况如何处理
   *
 * */
   int partition(int arr[],int left,int right){
    //1.设置基准值
    int pivot =arr[left];//取最左边的值当成基准值
    //2.进行比较，保证大的元素值在右边，小的在左边
    while (left<right){
        //先移动右边
        while(left<right && arr[right] >= pivot)
            right--;
        arr[left]=arr[right];
        //再移动左边
        while (left<right&& arr[left]<=pivot)
            left++;
        arr[right]=arr[left];
    }
    arr[left]=pivot;
    return left;
   }
   void quickSort(int arr[],int left,int right){
    if(left<right){
        //1.划分
        int pivotPos = partition(arr,left,right);
        //2.递归调用
        quickSort(arr,left,pivotPos-1);
        quickSort(arr,pivotPos+1,right);
    }

}

int main() {
    int arr[5]={23,123,51,22,45};
    quickSort(arr,0,4);
    //printf("Hello, World!\n");
    return 0;
}